#pragma once
#include "stdafx.h"

using namespace std;


/*======================================================================*/
/*						 Linked List */
/*======================================================================*/

/* ***********
 * PRIVATE *
 ************/
TList::TList()
{
	_head	=	0;//_NULL_LINK;
	_tail	=	0;//_NULL_LINK;
	_Count	=	0;
};

TList* TList::Copy()
{
	TList* copy = new TList();
	TLink* lnk = _head;
	while (lnk!=0)
	{
		copy->AddLast(lnk->_data.c_str());
		lnk=lnk->_next;
	};
	return copy;
};

TList::~TList()
{
	while (_head != 0)
	{
		TLink* temp=_head->_next;
		delete _head;
		_head=temp;
		_Debug_COUNTLINKS--;
	};	
};
int TList::Sort(int sens)
{
	if (_head==_tail) return 0;
	if (sens<0) return SortListDESC(this);
	return SortListASC(this);
};

TLink* TList::AddLast(const char* pValue)
{
	TLink* lnk		=	new TLink();
	lnk->_data		=	pValue;
	lnk->_list		=	this;
	
	if (_head==0)
	{
		_head		=	lnk;
		lnk->_prev	=	0;
	}
	else
	{
		_tail->_next=	lnk;
		lnk->_prev	=	_tail;
	};
	_tail			=	lnk;
	lnk->_next		=	0;
	_Count++;
	_Debug_COUNTLINKS++;
	return lnk;
};

TLink* TList::AddLast(const char* pValue, const char* pKey)
{
	TLink* lnk		=	new TLink();
	lnk->_data		=	pValue;
	lnk->_key		=	pKey;
	lnk->_list		=	this;
	
	if (_head==0)
	{
		_head		=	lnk;
		lnk->_prev	=	0;
	}
	else
	{
		_tail->_next=	lnk;
		lnk->_prev	=	_tail;
	};
	_tail			=	lnk;
	lnk->_next		=	0;
	_Count++;
	_Debug_COUNTLINKS++;
	return lnk;
};

TLink* TList::AddFirst(const char* pValue)
{
	TLink* lnk		=	new TLink();
	lnk->_data		=	pValue;
	lnk->_list		=	this;
	
	if (_tail==0)
	{
		_tail		=	lnk;
		lnk->_next	=	0;
	}
	else
	{
		_head->_prev=	lnk;
		lnk->_next	=	_head;
	};
	_head			=	lnk;
	lnk->_prev		=	0;
	_Count++;
	_Debug_COUNTLINKS++;
	return lnk;
};
TLink* TList::AddFirst(const char* pValue,const char* pKey)
{
	TLink* lnk		=	new TLink();
	lnk->_data		=	pValue;
	lnk->_key		=	pKey;
	lnk->_list		=	this;
	
	if (_tail==0)
	{
		_tail		=	lnk;
		lnk->_next	=	0;
	}
	else
	{
		_head->_prev=	lnk;
		lnk->_next	=	_head;
	};
	_head			=	lnk;
	lnk->_prev		=	0;
	_Count++;
	_Debug_COUNTLINKS++;
	return lnk;
};

TLink* TList::Find(const char* pValue)
{
	if (_head==0) return 0;
	TLink* l = _head;
	while (l!=0)
	{
		if (l->_data.compare(pValue)==0) return l;
		l=l->_next;
	};
	return 0;
};

TLink* TList::FindKey(const char* pKey)
{
	if (_head==0) return 0;
	TLink* l = _head;
	while (l!=0)
	{
		if (l->_key.compare(pKey)==0) return l;
		l=l->_next;
	};
	return 0;
};



TLink::TLink(){_key="";_data="";_Debug_COUNTLINKS++;};
TLink::~TLink(){Unlink(this);_Debug_COUNTLINKS--;};

TLink* NullLink(){return 0;};

inline void Unlink(TLink* lnk)
{
	TList* l = lnk->_list;
	
	if (lnk==l->_head)
	{
		if (lnk==l->_tail)
		{
			l->_head=0;
			l->_tail=0;
		}
		else
		{
			l->_head=lnk->_next;
			l->_head->_prev=0;
		};
	}
	else
	{
		if (lnk==l->_tail)
		{
			l->_tail=l->_tail->_prev;
			l->_tail->_next=0;
		}
		else
		{
			lnk->_next->_prev=lnk->_prev;
			lnk->_prev->_next=lnk->_next;
		};
	};
	lnk->_next=0;
	lnk->_prev=0;
	lnk->_list->_Count--;
};


int TLink::InsertAfter(TLink* after)
{
	if (_list!=after->_list) return 0;
	Unlink(this);
	TList* l=after->_list;
	if (after==l->_tail)
	{
		this->_next=0;
		this->_prev=after;
		after->_next=this;
		l->_tail=this;
	}
	else
	{
		this->_prev=after;
		after->_next->_prev=this;
		this->_next=after->_next;
		after->_next=this;
	};
	_list->_Count++;
	return 1;
};
int TLink::InsertBefore(TLink* before)
{
	if (_list!=before->_list) return 0;
	Unlink(this);
	TList* l=before->_list;
	if (before==l->_head)
	{
		this->_prev=0;
		this->_next=before;
		before->_prev=this;
		l->_head=this;
	}
	else
	{
		this->_next=before;
		before->_prev->_next=this;
		this->_prev=before->_prev;
		before->_prev=this;
	};
	_list->_Count++;
	return 1;
};
int TLink::Swap(TLink* l2)
{
	if (this==l2){return 0;};
	if (l2->_list!=_list){return 0;};
	
	if (_next==l2)
	{
		if (this==_list->_head){_list->_head=l2;};
		if (l2==_list->_tail){_list->_tail=this;};
		
		if (l2->_next != 0){l2->_next->_prev=this;};
		if (_prev != 0){_prev->_next=l2;};
		
		_next=l2->_next;
		l2->_prev=this->_prev;
		_prev=l2;
		l2->_next=this;
		
		return 1;
	};
	
	if (_prev==l2)
	{
		if (this==_list->_tail){_list->_tail=l2;};
		if (l2==_list->_head){_list->_head=this;};
		
		if (l2->_prev != 0){l2->_prev->_next=this;};
		if (_next != 0){_next->_prev=l2;};
		
		_prev=l2->_prev;
		l2->_next=this->_next;
		_next=l2;
		l2->_prev=this;
		
		return 1;
	};
	
	if ((_next==0) && (_prev==0)) return 0;
	
	// swap head/tail ?
	if (this==_list->_head)
	{
		_list->_head=l2;
	}
	else
	{
		if (l2==_list->_head)
		{
			_list->_head = this;
		}
	};
	
	if (this==_list->_tail)
	{
		_list->_tail=l2;
	}
	else
	{
		if (l2==_list->_tail)
		{
			_list->_tail = this;
		}
	};
	
	TLink* n1 = _next;
	TLink* p1 = _prev;
	TLink* n2 = l2->_next;
	TLink* p2 = l2->_prev;

	_next=n2;
	_prev=p2;
	l2->_next=n1;
	l2->_prev=p1;
	
	if (n1!=0){n1->_prev=l2;};
	if (p1!=0){p1->_next=l2;};
	if (n2!=0){n2->_prev=this;};
	if (p2!=0){p2->_next=this;};

	return 1;
};

TLink* TLink::Next(){if (this==_list->_tail){return 0;};return _next;};
TLink* TLink::Prev(){if (this==_list->_head){return 0;};return _prev;};


int SortListDESC(TList* list)
{
	bool done=false;

	while (done==false)
	{
		done=true;
		TLink* l1=list->_head->_next;
		TLink* l2;
		
		while (l1!=0)
		{
			l2=l1->_next;
			
			TLink* l3=l1->_prev;
			TLink* l4;
			while (l3!=0)
			{
				l4=l3->_prev;
				if (LinkCompare(l1,l3)>0)
				{
					l1->InsertBefore(l3);
					done=false;
				};
				l3=l4;
			};
			l1=l2;
		};
	};
	return 1;
};
int SortListASC(TList* list)
{
	bool done=false;

	while (done==false)
	{
		done=true;
		TLink* l1=list->_head->_next;
		TLink* l2;
		
		while (l1!=0)
		{
			l2=l1->_next;
			
			TLink* l3=l1->_prev;
			TLink* l4;
			while (l3!=0)
			{
				l4=l3->_prev;
				if (LinkCompare(l1,l3)<0)
				{
					l1->InsertBefore(l3);
					done=false;
				};
				l3=l4;
			};
			l1=l2;
		};
	};
	return 1;
};
